package halfDivide;


public class woodenCutDivide {
    public static void main(String[] args) {
        int[] L ={232,124,456};
        System.out.println(woodCut(L,7));
    }

    /**
     * 一推木头 切成k块
     * 1：截取后拿到最短的木头和最长的木头
     * 2：二分法 截取，找到截取满足木头块数最大的长度和最小的长度
     * @param L
     * @param k
     * @return
     */
    public static int woodCut(int[] L, int k){

        if (L==null ||L.length==0){
            return 0;
        }
        int start=1;
        int end=getMax(L);
        int mid;
        while(start+1<end){
            mid=start+(end-start)/2;
            int pieces=getPieces(L,mid);
            if (pieces>=k){
                start=mid;
            }else{
                end=mid;
            }
        }
        if (getPieces(L,end)>=k){
            return end;
        }
        if (getPieces(L,start)>=k){
            return start;
        }
        return 0;
    }

    /**
     * 拿到多少截木头
     * @param L
     * @param woodLength
     * @return
     */
    private static int getPieces(int[] L, int woodLength) {
        int pieces=0;
        for (int i : L) {
            pieces+=i/woodLength;
        }
        return pieces;
    }

    /**
     * 拿到最大的木头长度
     * @param L
     * @return
     */
    private static int getMax(int[] L) {
        int max=L[0];
        for (int i=1;i<L.length;i++){
            if (max<L[i]){
                max=L[i];
            }
        }
        return max;
    }
}
